package stack_queue.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 单调栈解决下一个更大元素问题
 **/
public class Num496 {
    // 单调栈
    private Stack<Integer> stack = new Stack<>();
    // 存储nums2中的每个元素(key)以及他的下一个更大元素值(value)
    private Map<Integer,Integer> map = new HashMap<>();
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 1.扫描nums2，维护单调栈，找到nums2的每个元素的下一个更大元素值
        // 倒着向前遍历是为了正向解决问题 => 向后寻找第一大元素
        for (int i = nums2.length - 1; i >= 0; i--) {
            // 此时栈不为空，且栈顶元素 <= 当前元素
            while (!stack.isEmpty() && stack.peek() <= nums2[i]) {
                stack.pop();
            }
            int nextGreatervalue = stack.isEmpty() ? -1 : stack.peek();
            // 处理完当前元素后，将当前元素压入栈，因为当前元素有可能是前面元素的下一个更大元素
            stack.push(nums2[i]);
            map.put(nums2[i],nextGreatervalue);
        }
        // 再次扫描nums1，取出每个元素对应的value就是结果集
        int[] ret = new int[nums1.length];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = map.get(nums1[i]);
        }
        return ret;
    }
}